{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Delete Nodes And Return Forest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #array #hash-table #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #数组 #哈希表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: delNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删点成林"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出二叉树的根节点&nbsp;<code>root</code>，树上每个节点都有一个不同的值。</p>\n",
    "\n",
    "<p>如果节点值在&nbsp;<code>to_delete</code>&nbsp;中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。</p>\n",
    "\n",
    "<p>返回森林中的每棵树。你可以按任意顺序组织答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/07/05/screen-shot-2019-07-01-at-53836-pm.png\" style=\"height: 150px; width: 237px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,4,5,6,7], to_delete = [3,5]\n",
    "<strong>输出：</strong>[[1,2,null,4],[6],[7]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,4,null,3], to_delete = [3]\n",
    "<strong>输出：</strong>[[1,2,4]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的节点数最大为&nbsp;<code>1000</code>。</li>\n",
    "\t<li>每个节点都有一个介于&nbsp;<code>1</code> 到&nbsp;<code>1000</code>&nbsp;之间的值，且各不相同。</li>\n",
    "\t<li><code>to_delete.length &lt;= 1000</code></li>\n",
    "\t<li><code>to_delete</code> 包含一些从&nbsp;<code>1</code> 到&nbsp;<code>1000</code>、各不相同的值。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [delete-nodes-and-return-forest](https://leetcode.cn/problems/delete-nodes-and-return-forest/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [delete-nodes-and-return-forest](https://leetcode.cn/problems/delete-nodes-and-return-forest/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6,7]\\n[3,5]', '[1,2,4,null,3]\\n[3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in to_delete:\n",
    "                return node\n",
    "            if node.left: ans.append(node.left)\n",
    "            if node.right : ans.append(node.right)\n",
    "            return None\n",
    "        if dfs(root): ans.append(root)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        \n",
    "        res=[]\n",
    "        temp=set(to_delete)\n",
    "        def dfs(node):\n",
    "            if node is None:return None\n",
    "            node.left=dfs(node.left)\n",
    "            node.right=dfs(node.right)\n",
    "            if node.val not in to_delete:return node\n",
    "            if node.left:res.append(node.left)\n",
    "            if node.right:res.append(node.right)\n",
    "            return None\n",
    "        if dfs(root):res.append(root)\n",
    "        return res\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root, to_delete):\n",
    "        to_delete_set = set(to_delete)\n",
    "        res = []\n",
    "\n",
    "        def helper(root, is_root):\n",
    "            if not root: return None\n",
    "            root_deleted = root.val in to_delete_set\n",
    "            if is_root and not root_deleted:\n",
    "                res.append(root)\n",
    "            root.left = helper(root.left, root_deleted)\n",
    "            root.right = helper(root.right, root_deleted)\n",
    "            return None if root_deleted else root\n",
    "        helper(root, True)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        s = set(to_delete)\n",
    "        ans = []\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return None\n",
    "            root.left, root.right = dfs(root.left), dfs(root.right)\n",
    "            if root.val not in s:\n",
    "                return root\n",
    "            if root.left:\n",
    "                ans.append(root.left)\n",
    "            if root.right:\n",
    "                ans.append(root.right)\n",
    "        if dfs(root):\n",
    "            ans.append(root)\n",
    "        return ans                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:\n",
    "        res = []\n",
    "        visit_queue = []\n",
    "        visit_queue.append(root)\n",
    "        root.parent = None\n",
    "        while len(visit_queue) != 0:\n",
    "            node = visit_queue[0]\n",
    "            del visit_queue[0]\n",
    "            if node.val in to_delete:\n",
    "                if node.parent != None:\n",
    "                    if node.parent[1] == 0:\n",
    "                        node.parent[0].left = None\n",
    "                    else:\n",
    "                        node.parent[0].right = None\n",
    "                if node.left != None:\n",
    "                    visit_queue.append(node.left)\n",
    "                    node.left.parent = None\n",
    "                if node.right != None:\n",
    "                    visit_queue.append(node.right)\n",
    "                    node.right.parent = None\n",
    "            else:            \n",
    "                if node.parent == None:\n",
    "                    res.append(node)\n",
    "                if node.left != None:\n",
    "                    visit_queue.append(node.left)\n",
    "                    node.left.parent = (node,0)\n",
    "                if node.right != None:\n",
    "                    visit_queue.append(node.right)\n",
    "                    node.right.parent = (node,1)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        # ans = []\n",
    "        # to_delete = set(to_delete) # 这样做查询的时间复杂度会降低成O(1)\n",
    "        # def dfs(node, is_root):\n",
    "        #     if not node:\n",
    "        #         return None\n",
    "        #     delete = node.val in to_delete\n",
    "        #     node.left = dfs(node.left, delete)\n",
    "        #     node.right = dfs(node.right, delete)\n",
    "        #     if delete:\n",
    "        #         return None\n",
    "        #     else:\n",
    "        #         if is_root:\n",
    "        #             ans.append(node)\n",
    "        #         return node\n",
    "        # dfs(root, True)\n",
    "        # return ans\n",
    "\n",
    "        ans = []\n",
    "        to_delete = set(to_delete)\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            # 后序遍历\n",
    "            node.left =dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in to_delete:\n",
    "                return node\n",
    "            if node.left:\n",
    "                ans.append(node.left)\n",
    "            if node.right:\n",
    "                ans.append(node.right)\n",
    "        if dfs(root):\n",
    "            ans.append(root)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        to_delete_set = set(to_delete)\n",
    "        roots = []\n",
    "        self.dfs(root, True, to_delete_set, roots)\n",
    "        return roots\n",
    "\n",
    "    def dfs(self, node: Optional[TreeNode], is_root: bool, to_delete_set: set[int], roots: List[TreeNode]) ->  Optional[TreeNode]:\n",
    "        if node == None:\n",
    "            return None\n",
    "        delete = node.val in to_delete_set\n",
    "        node.left = self.dfs(node.left, delete, to_delete_set, roots)\n",
    "        node.right = self.dfs(node.right, delete, to_delete_set, roots)\n",
    "        if delete:\n",
    "            return None\n",
    "        else:\n",
    "            if is_root:\n",
    "                roots.append(node)\n",
    "            return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "\n",
    "        def dfs(root: Optional[TreeNode], is_root: bool, to_delete: List[int], res):\n",
    "            if root == None:\n",
    "                return None\n",
    "            child_is_root = root.val in to_delete\n",
    "            root.left = dfs(root.left, child_is_root, to_delete, res)\n",
    "            root.right = dfs(root.right, child_is_root, to_delete, res)\n",
    "            if child_is_root:\n",
    "                return None\n",
    "            else:\n",
    "                if is_root:\n",
    "                    self.res.append(root)\n",
    "                return root\n",
    "\n",
    "        dfs(root, True, to_delete, self.res)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        to_delete_set = set(to_delete)\n",
    "        roots = []\n",
    "        self.dfs(root, True, to_delete_set, roots)\n",
    "        return roots\n",
    "\n",
    "    def dfs(self, node: Optional[TreeNode], is_root: bool, to_delete_set: set[int], roots: List[TreeNode]) ->  Optional[TreeNode]:\n",
    "        if node == None:\n",
    "            return None\n",
    "        delete = node.val in to_delete_set\n",
    "        node.left = self.dfs(node.left, delete, to_delete_set, roots)\n",
    "        node.right = self.dfs(node.right, delete, to_delete_set, roots)\n",
    "        if delete:\n",
    "            return None\n",
    "        else:\n",
    "            if is_root:\n",
    "                roots.append(node)\n",
    "            return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        res = []\n",
    "        \n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if root == None:\n",
    "                return None\n",
    "\n",
    "            for v in to_delete:\n",
    "                if root.val == v: #要删除\n",
    "                    left = dfs(root.left)\n",
    "                    right = dfs(root.right)\n",
    "                    if left:\n",
    "                        res.append(left)\n",
    "                    if right:\n",
    "                        res.append(right)\n",
    "                    return None\n",
    "            \n",
    "            root.left = dfs(root.left)\n",
    "            root.right = dfs(root.right)\n",
    "            return root\n",
    "        node = dfs(root)\n",
    "        if node:\n",
    "            res.append(dfs(root))   \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        roots = []\n",
    "\n",
    "        def dfs(node, is_root, roots):\n",
    "            if not node:\n",
    "                return None\n",
    "            #nonlocal to_delete\n",
    "            delete = node.val in to_delete\n",
    "            node.left = dfs(node.left, delete, roots)\n",
    "            node.right = dfs(node.right, delete, roots)\n",
    "\n",
    "            if delete:\n",
    "                return None\n",
    "            else:\n",
    "                if is_root:\n",
    "                    roots.append(node)\n",
    "                return node\n",
    "\n",
    "        dfs(root, True, roots)\n",
    "        return roots\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete)\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            root.left = dfs(root.left)\n",
    "            root.right = dfs(root.right)\n",
    "            if root.val not in s:\n",
    "                return root\n",
    "            if root.left:\n",
    "                ans.append(root.left)\n",
    "            if root.right:\n",
    "                ans.append(root.right)\n",
    "            return None\n",
    "        \n",
    "        if dfs(root):\n",
    "            ans.append(root)\n",
    "        return ans\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete)\n",
    "        def dfs(node: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "            if node is None: return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in s: return node\n",
    "            if node.left: ans.append(node.left)\n",
    "            if node.right: ans.append(node.right)\n",
    "            return None\n",
    "        if dfs(root): ans.append(root)\n",
    "        return ans\n",
    "\n",
    "        # q = deque([root])\n",
    "        # to_delete = set(to_delete)\n",
    "        # res = root\n",
    "        # while q:\n",
    "        #     parent = q.popleft()\n",
    "        #     left_son = None\n",
    "        #     right_son = None\n",
    "        #     if parent == None and parent.val in to_delete:\n",
    "        #         return None\n",
    "        #     if parent.left:\n",
    "        #         left_son = parent.left\n",
    "        #         if left_son.val in to_delete:\n",
    "        #             to_delete.remove(left_son.val)\n",
    "        #             parent.left = None\n",
    "        #         else:\n",
    "        #             q.append(left_son)\n",
    "\n",
    "        #     if parent.right:\n",
    "        #         right_son = parent.right\n",
    "        #         if right_son.val in to_delete:\n",
    "        #             to_delete.remove(right_son.val)\n",
    "        #             parent.right = None\n",
    "        #         else:\n",
    "        #             q.append(right_son)\n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s =set(to_delete)\n",
    "        def dfs(node:Optional[TreeNode]) -> Optional[TreeNode]: #后序遍历\n",
    "            if node is None: return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "\n",
    "            if node.val not in s: return node #\n",
    "            if node.left: ans.append(node.left) # 判断当前节点是否被删除， 没有就加入答案\n",
    "            if node.right: ans.append(node.right)\n",
    "\n",
    "            return None\n",
    "        if dfs(root): ans.append(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            root.left = dfs(root.left)\n",
    "            root.right = dfs(root.right)\n",
    "            if root.val not in to_delete:\n",
    "                return root\n",
    "            if root.left:\n",
    "                ans.append(root.left)\n",
    "            if root.right:\n",
    "                ans.append(root.right)\n",
    "            return None\n",
    "        \n",
    "        if dfs(root):\n",
    "            ans.append(root)\n",
    "        return ans\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val in to_delete:\n",
    "                nonlocal ans\n",
    "                if node.left:\n",
    "                    ans.append(node.left)\n",
    "                if node.right:\n",
    "                    ans.append(node.right)\n",
    "                return None\n",
    "            return node\n",
    "        dfs(root)\n",
    "        if root and root.val not in to_delete:\n",
    "            ans.append(root)\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        to_delete_set = set(to_delete)\n",
    "        res = []\n",
    "\n",
    "        def helper(root, is_root):\n",
    "            if not root: return None\n",
    "            root_deleted = root.val in to_delete_set\n",
    "            if is_root and not root_deleted:\n",
    "                res.append(root)\n",
    "            root.left = helper(root.left, root_deleted)\n",
    "            root.right = helper(root.right, root_deleted)\n",
    "            return None if root_deleted else root\n",
    "        helper(root, True)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        def dfs(node):\n",
    "            if not node: return \n",
    "\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in to_delete: return node\n",
    "            if node.left: ans.append(node.left)\n",
    "            if node.right: ans.append(node.right)\n",
    "\n",
    "            return None \n",
    "\n",
    "        if dfs(root): ans.append(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        # 哈希表用于查询当前节点是否需要被删除\n",
    "        s = set(to_delete)\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            root.left = dfs(root.left)\n",
    "            root.right = dfs(root.right)\n",
    "            # 当前节点无需被删除, 直接返回给上一层\n",
    "            if root.val not in s:\n",
    "                return root\n",
    "            # 当前节点需要被删除, res记录左右节点, 删除当前节点并返回null给上一层\n",
    "            if root.left:\n",
    "                ans.append(root.left)\n",
    "            if root.right:\n",
    "                ans.append(root.right)\n",
    "            return None\n",
    "        \n",
    "        # 如果递归后不为空，则加入结果集\n",
    "        if dfs(root):\n",
    "            ans.append(root)\n",
    "        return ans\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        to_delete_set = set(to_delete)\n",
    "        self.roots = []\n",
    "        self.dfs(root, True, to_delete_set)\n",
    "        return self.roots\n",
    "    \n",
    "    def dfs(self, root, is_root, to_delete_set):\n",
    "        if root is None:\n",
    "            return None\n",
    "        \n",
    "        delete = root.val in to_delete_set\n",
    "        root.left = self.dfs(root.left, delete, to_delete_set)\n",
    "        root.right = self.dfs(root.right, delete, to_delete_set)\n",
    "        if delete:\n",
    "            return None\n",
    "        else:\n",
    "            if is_root:\n",
    "                self.roots.append(root)\n",
    "            return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete)\n",
    "\n",
    "        def dfs(node: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "            if node is None:\n",
    "                return\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in s:\n",
    "                return node\n",
    "            if node.left:\n",
    "                ans.append(node.left)\n",
    "            if node.right:\n",
    "                ans.append(node.right)\n",
    "            return\n",
    "\n",
    "        if dfs(root):\n",
    "            ans.append(root)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        # root.left = None\n",
    "        res = []\n",
    "        # root.left = None\n",
    "        # print(root)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        def dfs(root,flag = True):\n",
    "            if root == None:\n",
    "                return\n",
    "            if root.val in to_delete:\n",
    "                # print(root.val)\n",
    "                \n",
    "                root.left = dfs(root.left,flag=False)\n",
    "                root.right =dfs(root.right,flag = False)\n",
    "                # print(f\"狗{root.left,root.right}\")\n",
    "                if root.left==None and root.right == None:\n",
    "                    pass\n",
    "                elif root.left and root.right:\n",
    "                    # print(f\"执行{root.left.val}\")\n",
    "                    res.append(root.left)\n",
    "                    res.append(root.right)\n",
    "                    \n",
    "                elif root.left:\n",
    "                    res.append(root.left)\n",
    "                else :\n",
    "                    res.append(root.right)\n",
    "                to_delete.remove(root.val)\n",
    "                root = None\n",
    "                \n",
    "                return root\n",
    "            else:\n",
    "                \n",
    "                root.left = dfs(root.left,flag=False)\n",
    "                root.right = dfs(root.right,flag = False)\n",
    "                if flag==True:\n",
    "                    res.append(root)\n",
    "                return root\n",
    "\n",
    "            if flag == True and root:\n",
    "                print(\"好人\")\n",
    "                res.append(root)\n",
    "        \n",
    "        dfs(root)\n",
    "        # print(to_delete)\n",
    "        \n",
    "        return res\n",
    "    \n",
    "                \n",
    "\n",
    "                \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete)\n",
    "        def dfs(node: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "            if node is None: return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in s: return node\n",
    "            if node.left: ans.append(node.left)\n",
    "            if node.right: ans.append(node.right)\n",
    "            return None\n",
    "        if dfs(root): ans.append(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        to_delete = set(to_delete)\n",
    "        forest = []\n",
    "        def dsf(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            \n",
    "            root.left = dsf(root.left)\n",
    "            root.right = dsf(root.right)\n",
    "            if root.val in to_delete:\n",
    "                if root.left:\n",
    "                    forest.append(root.left)\n",
    "                if root.right:\n",
    "                    forest.append(root.right)\n",
    "                return None\n",
    "            else:\n",
    "                return root\n",
    "\n",
    "        if dsf(root): forest.append(root)\n",
    "        return forest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        def dfs(node,is_root):\n",
    "            if not node:\n",
    "                return None\n",
    "            delete = node.val in to_delete\n",
    "\n",
    "            if is_root and not delete:\n",
    "                result.append(node)\n",
    "\n",
    "            node.left = dfs(node.left,delete)\n",
    "            node.right = dfs(node.right,delete)\n",
    "\n",
    "            return None if delete else node\n",
    "        \n",
    "        result = []\n",
    "        to_delete = set(to_delete)\n",
    "        dfs(root,True)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        to_delete = set(to_delete)\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in to_delete:\n",
    "                return node\n",
    "            else:\n",
    "                if node.left:\n",
    "                    ans.append(node.left)\n",
    "                if node.right:\n",
    "                    ans.append(node.right)\n",
    "            return None\n",
    "        if dfs(root):\n",
    "            ans.append(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete)\n",
    "\n",
    "        def dfs(root: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "            if root is None:\n",
    "                return\n",
    "            root.left = dfs(root.left)\n",
    "            root.right = dfs(root.right)\n",
    "            if root.val not in s:\n",
    "                return root\n",
    "            if root.left:\n",
    "                ans.append(root.left)\n",
    "            if root.right:\n",
    "                ans.append(root.right)\n",
    "            return\n",
    "\n",
    "        if dfs(root):\n",
    "            ans.append(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete)\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in s:\n",
    "                return node\n",
    "            if node.left:\n",
    "                ans.append(node.left)\n",
    "            if node.right:\n",
    "                ans.append(node.right)\n",
    "            return None\n",
    "        if dfs(root):\n",
    "            ans.append(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "\n",
    "        def helper(root, to_delete, forest):\n",
    "            if not root:\n",
    "                return None\n",
    "            root.left = helper(root.left, to_delete, forest)\n",
    "            root.right = helper(root.right, to_delete, forest)\n",
    "            if root.val in to_delete:\n",
    "                if root.left:\n",
    "                    forest.append(root.left)\n",
    "                if root.right:\n",
    "                    forest.append(root.right)\n",
    "                root = None\n",
    "            return root\n",
    "        forest = []\n",
    "        root = helper(root, to_delete, forest)\n",
    "        if root:\n",
    "            forest.append(root)\n",
    "        return forest\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        def dfs(father, root, is_root: bool):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.left:dfs(root, root.left, root.val in to_delete)\n",
    "            if root.right:dfs(root, root.right, root.val in to_delete)\n",
    "            if root.val in to_delete:\n",
    "                delete(father, root)\n",
    "            else:\n",
    "                if is_root:\n",
    "                    ans.append(root)\n",
    "        \n",
    "        def delete(father, son):\n",
    "            if not father:return\n",
    "            if father.left == son:\n",
    "                father.left = None\n",
    "            else:\n",
    "                father.right = None\n",
    "        \n",
    "        to_delete = set(to_delete)\n",
    "        dfs(None, root, True)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans, need_delete = [], set(to_delete)\n",
    "        def dfs(node, added):\n",
    "            if not node: return\n",
    "            \n",
    "            if node.val in need_delete:\n",
    "                dfs(node.left, False)\n",
    "                dfs(node.right, False)\n",
    "                return\n",
    "            \n",
    "            if not added:\n",
    "                ans.append(node)\n",
    "            left = node.left\n",
    "            right = node.right\n",
    "            if left and left.val in need_delete:\n",
    "                node.left = None\n",
    "            if right and right.val in need_delete:\n",
    "                node.right = None    \n",
    "            dfs(right, True)\n",
    "            dfs(left, True)\n",
    "        \n",
    "        dfs(root, False)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete)\n",
    "        def dfs(root:Optional[TreeNode])->Optional[TreeNode]:\n",
    "            if root is None:return None\n",
    "            root.left = dfs(root.left)\n",
    "            root.right = dfs(root.right)\n",
    "            if root.val not in s:return root\n",
    "            if root.left:ans.append(root.left)\n",
    "            if root.right:ans.append(root.right)\n",
    "            return None\n",
    "        if dfs(root):ans.append(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        \n",
    "        def dfs(root) -> Optional[TreeNode]:\n",
    "            if not root:\n",
    "                return None\n",
    "            # recall sub trees first\n",
    "            root.left = dfs(root.left)\n",
    "            root.right = dfs(root.right)\n",
    "            # check if delete root\n",
    "            if root.val in to_delete:\n",
    "                # delete root, record sub tree(if exist)\n",
    "                if root.left:\n",
    "                    ans.append(root.left)\n",
    "                if root.right:\n",
    "                    ans.append(root.right)\n",
    "                return None\n",
    "            return root\n",
    "        to_delete = set(to_delete)\n",
    "        ans = []\n",
    "        if dfs(root):\n",
    "            ans.append(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "\n",
    "        to_delete = set(to_delete)\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return\n",
    "\n",
    "            root.left = dfs(root.left)\n",
    "            root.right=dfs(root.right)\n",
    "            \n",
    "            if root.val in to_delete:\n",
    "                if root.left:\n",
    "                    res.append(root.left)\n",
    "                if root.right:\n",
    "                    res.append(root.right)\n",
    "                return None\n",
    "            return root\n",
    "        root = dfs(root)\n",
    "        if root:\n",
    "            res.append(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        result = []\n",
    "\n",
    "        def dfs(root, parent, posision):\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            if root.left:\n",
    "                dfs(root.left, root, 'left')\n",
    "            if root.right:\n",
    "                dfs(root.right, root, 'right')\n",
    "            if root.val in to_delete:\n",
    "                if root.left:\n",
    "                    result.append(root.left)\n",
    "                if root.right:\n",
    "                    result.append(root.right)\n",
    "                \n",
    "                if posision == 'left':\n",
    "                    parent.left = None\n",
    "                \n",
    "                if posision == 'right':\n",
    "                    parent.right = None\n",
    "\n",
    "                if posision == 'root':\n",
    "                    parent.val = -1\n",
    "                \n",
    "        dfs(root, root, 'root')\n",
    "\n",
    "        if root.val != -1:\n",
    "            result.append(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        # 存储头结点，然后在依次遍历头结点\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        self.trac(root,to_delete,res)\n",
    "        if root.val not in to_delete:\n",
    "            res.append(root)\n",
    "        # print(res)\n",
    "        return res\n",
    "        \n",
    "    def trac(self,root,to_delete,res):\n",
    "        \n",
    "        if not root:\n",
    "            return None\n",
    "        # print(root.val)\n",
    "        left = self.trac(root.left,to_delete,res)\n",
    "        right = self.trac(root.right,to_delete,res)\n",
    "        if root.val in to_delete:\n",
    "            # print(root.val)\n",
    "            if left:\n",
    "                res.append(left)\n",
    "                root.left = None\n",
    "            if right:\n",
    "                res.append(right)\n",
    "                root.right = None\n",
    "            return None\n",
    "        else:\n",
    "            root.left = left\n",
    "            root.right = right\n",
    "            return root\n",
    "            \n",
    "            \n",
    "            \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans=[]\n",
    "        s=set(to_delete)\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "            node.left=dfs(node.left)\n",
    "            node.right=dfs(node.right)\n",
    "            if node.val not in s :return node\n",
    "            if node.left:ans.append(node.left)\n",
    "            if node.right:ans.append(node.right)\n",
    "            return None\n",
    "        if dfs(root):ans.append(root)\n",
    "        return ans        \n",
    "\n",
    "        return ans                 \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        to_delete_set = set(to_delete)\n",
    "        roots = []\n",
    "        self.dfs(root, True, to_delete_set, roots)\n",
    "        return roots\n",
    "\n",
    "    def dfs(self, node: Optional[TreeNode], is_root: bool, to_delete_set: set[int], roots: List[TreeNode]) ->  Optional[TreeNode]:\n",
    "        if node == None:\n",
    "            return None\n",
    "        delete = node.val in to_delete_set\n",
    "        node.left = self.dfs(node.left, delete, to_delete_set, roots)\n",
    "        node.right = self.dfs(node.right, delete, to_delete_set, roots)\n",
    "        if delete:\n",
    "            return None\n",
    "        else:\n",
    "            if is_root:\n",
    "                roots.append(node)\n",
    "            return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete)\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in s:\n",
    "                return node\n",
    "            if node.left:\n",
    "                ans.append(node.left)\n",
    "            if node.right:\n",
    "                ans.append(node.right)\n",
    "            return None\n",
    "        if dfs(root):\n",
    "            ans.append(root)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        res = []\n",
    "        mp = set(to_delete)\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            root.left = dfs(root.left)\n",
    "            root.right = dfs(root.right)\n",
    "            if root.val not in mp: return root\n",
    "            if root.left: res.append(root.left)\n",
    "            if root.right: res.append(root.right)\n",
    "            return None\n",
    "            \n",
    "        if dfs(root): res.append(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete)\n",
    "        def dfs(node: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "            if node is None: return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in s: return node\n",
    "            if node.left: ans.append(node.left)\n",
    "            if node.right: ans.append(node.right)\n",
    "            return None\n",
    "        if dfs(root): ans.append(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = to_delete\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in s:\n",
    "                return node\n",
    "            if node.left:ans.append(node.left)\n",
    "            if node.right:ans.append(node.right)\n",
    "            return None\n",
    "        if dfs(root):\n",
    "            ans.append(root)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\r\n",
    "        ans = []\r\n",
    "        s = set(to_delete)\r\n",
    "        def dfs(node: Optional[TreeNode]) -> Optional[TreeNode]:\r\n",
    "            if node is None: return None\r\n",
    "            node.left = dfs(node.left)\r\n",
    "            node.right = dfs(node.right)\r\n",
    "            if node.val not in s: return node\r\n",
    "            else:\r\n",
    "                if node.left: ans.append(node.left)\r\n",
    "                if node.right: ans.append(node.right)\r\n",
    "            return None\r\n",
    "        if dfs(root): ans.append(root)\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    \n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        to_delete = set(to_delete)\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in to_delete:\n",
    "                return node\n",
    "            if node.left:\n",
    "                ans.append(node.left)\n",
    "            if node.right:\n",
    "                ans.append(node.right)\n",
    "            return None\n",
    "        root_is_preserve = dfs(root)\n",
    "        if root_is_preserve:\n",
    "            ans.append(root)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans=[]\n",
    "        s=set(to_delete)\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None\n",
    "            node.left=dfs(node.left)\n",
    "            node.right=dfs(node.right)\n",
    "            if node.val not in s:\n",
    "                return node\n",
    "            if node.left: ans.append(node.left)\n",
    "            if node.right: ans.append(node.right)\n",
    "            return None\n",
    "        if dfs(root): ans.append(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        def find(node):\n",
    "            nonlocal ans\n",
    "            if node is None:\n",
    "                return\n",
    "            if node.val in to_delete:\n",
    "                find(node.left)\n",
    "                find(node.right)\n",
    "                if node.left and node.left.val not in to_delete:\n",
    "                    ans.append(node.left)\n",
    "                if node.right and node.right.val not in to_delete:\n",
    "                    ans.append(node.right)\n",
    "                return None\n",
    "            else:\n",
    "                node.left = find(node.left)\n",
    "                node.right = find(node.right)\n",
    "                return node\n",
    "        root = find(root)\n",
    "        if root and root not in to_delete:\n",
    "            ans.append(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete) \n",
    "        #快速判断节点值是否在to_delete中 -> 丢进哈希表中\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in s:\n",
    "                return node\n",
    "            if node.left:ans.append(node.left)\n",
    "            if node.right:ans.append(node.right)\n",
    "            return None\n",
    "        if dfs(root):\n",
    "            ans.append(root)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        delete_val = set(to_delete)#由于值唯一 因此可以直接处理值\n",
    "        rs = []\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val in delete_val:\n",
    "                if node.left:\n",
    "                    rs.append(node.left)\n",
    "                if node.right:\n",
    "                    rs.append(node.right)\n",
    "                return None\n",
    "            return node\n",
    "        root = dfs(root)\n",
    "        if root:\n",
    "            rs.append(root)\n",
    "        return rs\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        to_delete = set(to_delete)\n",
    "        res = []\n",
    "        def dfs(node):\n",
    "            if not node: return None\n",
    "            if node.val in to_delete:\n",
    "                left = dfs(node.left)\n",
    "                right = dfs(node.right)\n",
    "                if left:\n",
    "                    res.append(left)\n",
    "                if right:\n",
    "                    res.append(right)\n",
    "                return None\n",
    "            else:\n",
    "                node.left = dfs(node.left)\n",
    "                node.right = dfs(node.right)\n",
    "                return node\n",
    "        tmp = dfs(root)\n",
    "        if tmp:\n",
    "            res.append(tmp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete)\n",
    "        def dfs(node: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "            if node is None: return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in s: return node\n",
    "            if node.left: ans.append(node.left)\n",
    "            if node.right: ans.append(node.right)\n",
    "            return None\n",
    "        if dfs(root): ans.append(root)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.flag =True\n",
    "        self.t = True\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        if self.flag:\n",
    "            self.flag = False\n",
    "            if root.val in to_delete:\n",
    "                self.delNodes(root,to_delete)\n",
    "                if root.left:\n",
    "                    self.res.append(root.left)\n",
    "                if root.right:\n",
    "                    self.res.append(root.right)\n",
    "                self.root = None\n",
    "            else:\n",
    "                self.res.append(root)\n",
    "            \n",
    "        if root:\n",
    "            if root.left:\n",
    "                self.delNodes(root.left,to_delete)\n",
    "                if root.left.val in to_delete:\n",
    "                    if root.left.left:\n",
    "                        self.res.append(root.left.left)\n",
    "                    if root.left.right:\n",
    "                        self.res.append(root.left.right)\n",
    "                    root.left = None\n",
    "               \n",
    "            if root.right:\n",
    "                self.delNodes(root.right,to_delete)\n",
    "                if root.right.val in to_delete:\n",
    "                    if root.right.left:\n",
    "                        self.res.append(root.right.left)\n",
    "                    if root.right.right:\n",
    "                        self.res.append(root.right.right)\n",
    "                    root.right = None\n",
    "\n",
    "        return self.res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        to_delete_set = set(to_delete)\n",
    "        roots = []\n",
    "        self.dfs(root, True, to_delete_set, roots)\n",
    "        return roots\n",
    "\n",
    "    def dfs(self, node: Optional[TreeNode], is_root: bool, to_delete_set: set[int], roots: List[TreeNode]) ->  Optional[TreeNode]:\n",
    "        if node == None:\n",
    "            return None\n",
    "        delete = node.val in to_delete_set\n",
    "        node.left = self.dfs(node.left, delete, to_delete_set, roots)\n",
    "        node.right = self.dfs(node.right, delete, to_delete_set, roots)\n",
    "        if delete:\n",
    "            return None\n",
    "        else:\n",
    "            if is_root:\n",
    "                roots.append(node)\n",
    "            return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete) \n",
    "        #快速判断节点值是否在to_delete中 -> 丢进哈希表中\n",
    "        #此时为后序遍历 因为可能存在ans不需要根节点但是需要他的左右儿子\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in s:\n",
    "                return node\n",
    "            if node.left:ans.append(node.left)\n",
    "            if node.right:ans.append(node.right)\n",
    "            return None\n",
    "        if dfs(root):\n",
    "            ans.append(root)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        to_delete_set = set(to_delete)\n",
    "        roots = []\n",
    "        def dfs(node, is_root):\n",
    "            if node == None:\n",
    "                return None\n",
    "            delete = node.val in to_delete_set\n",
    "            node.left = dfs(node.left, delete)\n",
    "            node.right = dfs(node.right, delete)\n",
    "            if delete:\n",
    "                return None\n",
    "            else:\n",
    "                if is_root:\n",
    "                    roots.append(node)\n",
    "                return node\n",
    "        dfs(root, True)\n",
    "        return roots\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "#         to_delete_set = set(to_delete)\n",
    "#         roots = []\n",
    "#         self.dfs(root, True, to_delete_set, roots)\n",
    "#         return roots\n",
    "\n",
    "#     def dfs(self, node: Optional[TreeNode], is_root: bool, to_delete_set: set[int], roots: List[TreeNode]) ->  Optional[TreeNode]:\n",
    "#         if node == None:\n",
    "#             return None\n",
    "#         delete = node.val in to_delete_set\n",
    "#         node.left = self.dfs(node.left, delete, to_delete_set, roots)\n",
    "#         node.right = self.dfs(node.right, delete, to_delete_set, roots)\n",
    "#         if delete:\n",
    "#             return None\n",
    "#         else:\n",
    "#             if is_root:\n",
    "#                 roots.append(node)\n",
    "#             return node\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete)\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in s:\n",
    "                return node\n",
    "            if node.left:ans.append(node.left)\n",
    "            if node.right:ans.append(node.right)\n",
    "            return None\n",
    "        if dfs(root):\n",
    "            ans.append(root)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        result=[]\n",
    "        s=set(to_delete)\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "            node.left=dfs(node.left)\n",
    "            node.right=dfs(node.right)\n",
    "            if node.val not in s:\n",
    "                return node\n",
    "            if node.left:\n",
    "                result.append(node.left)\n",
    "            if node.right:\n",
    "                result.append(node.right)\n",
    "            return None\n",
    "        if dfs(root):\n",
    "            result.append(root)\n",
    "        return result\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        \n",
    "        rs = []\n",
    "        def travel(node, parent, position):\n",
    "            # node: 当前节点\n",
    "            # parent: 父节点\n",
    "            # positon: 当前节点位置 left / right\n",
    "            if node.val in to_delete:\n",
    "                if parent is not None:\n",
    "                    # 父节点删除子节点\n",
    "                    if position == 'left':\n",
    "                        parent.left = None\n",
    "                    else:\n",
    "                        parent.right = None\n",
    "                if node.left is not None:\n",
    "                    # 子节点各自成树\n",
    "                    travel(node.left, None, None)\n",
    "                if node.right is not None:\n",
    "                    travel(node.right, None, None)\n",
    "            else:\n",
    "                if parent is None:\n",
    "                    # 当前节点没有被删, 并且没有父节点, 则其就是一棵树的根节点\n",
    "                    rs.append(node)\n",
    "                if node.left is not None:\n",
    "                    # 遍历子节点\n",
    "                    travel(node.left, node, \"left\")\n",
    "                if node.right is not None:\n",
    "                    travel(node.right, node, \"right\")\n",
    "        travel(root, None, None)\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return None\n",
    "            if root.left:\n",
    "                root.left = dfs(root.left)\n",
    "            if root.right:\n",
    "                root.right = dfs(root.right)\n",
    "            if root.val in to_delete:\n",
    "                if root.left:\n",
    "                    ans.append(root.left)\n",
    "                if root.right:\n",
    "                    ans.append(root.right)\n",
    "                return None\n",
    "            else:\n",
    "                return root\n",
    "        if not root:\n",
    "            return ans\n",
    "        if root.val not in to_delete:\n",
    "            ans.append(root)\n",
    "        dfs(root)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# 写一个 DFS（后序遍历）：\n",
    "\n",
    "# 更新左儿子（右儿子）为递归左儿子（右儿子）的返回值。\n",
    "# 如果当前节点被删除，那么就检查左儿子（右儿子）是否被删除，如果没被删除，就加入答案。\n",
    "# 如果当前节点被删除，返回空节点，否则返回当前节点。\n",
    "# 最后，如果根节点没被删除，把根节点加入答案。\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/delete-nodes-and-return-forest/solutions/2289131/he-shi-ji-lu-da-an-pythonjavacgo-by-endl-lpcd/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        def dfs(node) -> TreeNode:\n",
    "            if not node:\n",
    "                return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in cache:\n",
    "                return node\n",
    "            else:\n",
    "                if node.left:\n",
    "                    res.append(node.left)\n",
    "                if node.right:\n",
    "                    res.append(node.right)\n",
    "                return None\n",
    "                        \n",
    "        res = []\n",
    "        cache = set(to_delete)\n",
    "        if dfs(root):\n",
    "            res.append(root)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete)\n",
    "        def dfs(node):\n",
    "            if node is None: return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in s: return node\n",
    "            if node.left: ans.append(node.left)\n",
    "            if node.right: ans.append(node.right)\n",
    "            return None\n",
    "\n",
    "        if dfs(root): ans.append(root)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete)\n",
    "        def dfs(node):\n",
    "            if node == None:\n",
    "                return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in s:\n",
    "                return node\n",
    "            if node.left:ans.append(node.left)\n",
    "            if node.right:ans.append(node.right)\n",
    "            if not node:\n",
    "                return None\n",
    "        if dfs(root):\n",
    "            ans.append(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        to_delete = set(to_delete)\n",
    "        if root.val not in to_delete:\n",
    "            ans.append(root)\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            if dfs(node.left):\n",
    "                node.left = None\n",
    "            elif node.left and node.val in to_delete:\n",
    "                ans.append(node.left)\n",
    "\n",
    "            if dfs(node.right):\n",
    "                node.right = None\n",
    "            elif node.right and node.val in to_delete:\n",
    "                ans.append(node.right)\n",
    "\n",
    "            return node.val in to_delete\n",
    "        \n",
    "        dfs(root)\n",
    "        return ans\n",
    "        \n",
    "                \n",
    "            \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        path=[]\n",
    "        table=set()\n",
    "        for to in to_delete:\n",
    "            table.add(to)\n",
    "        def dfs(root: Optional[TreeNode],path: List[int])->TreeNode:\n",
    "            if root is None:\n",
    "                return root\n",
    "            else:\n",
    "                left=dfs(root.left,path)\n",
    "                right=dfs(root.right,path)\n",
    "                root.left=left\n",
    "                root.right=right\n",
    "                if root.val not in table:\n",
    "                    return root\n",
    "                if root.left:\n",
    "                    path.append(root.left)\n",
    "                if root.right:\n",
    "                    path.append(root.right)\n",
    "                return None\n",
    "        Tree=dfs(root,path)\n",
    "        if Tree:\n",
    "            path.append(Tree)\n",
    "        return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# 写一个 DFS（后序遍历）：\n",
    "\n",
    "# 更新左儿子（右儿子）为递归左儿子（右儿子）的返回值。\n",
    "# 如果当前节点被删除，那么就检查左儿子（右儿子）是否被删除，如果没被删除，就加入答案。\n",
    "# 如果当前节点被删除，返回空节点，否则返回当前节点。\n",
    "# 最后，如果根节点没被删除，把根节点加入答案。\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/delete-nodes-and-return-forest/solutions/2289131/he-shi-ji-lu-da-an-pythonjavacgo-by-endl-lpcd/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        def dfs(node) -> TreeNode:\n",
    "            if not node:\n",
    "                return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in cache:\n",
    "                return node\n",
    "            if node.left:\n",
    "                res.append(node.left)\n",
    "            if node.right:\n",
    "                res.append(node.right)\n",
    "            return None\n",
    "                        \n",
    "        res = []\n",
    "        cache = set(to_delete)\n",
    "        if dfs(root):\n",
    "            res.append(root)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        to_delete = set(to_delete)\n",
    "\n",
    "        que = deque()\n",
    "        que.append((root, None, ''))\n",
    "\n",
    "        res = []\n",
    "        if root.val not in to_delete:\n",
    "            res.append(root)\n",
    "\n",
    "        while que:\n",
    "            node, parent, child = que.popleft()\n",
    "            val, left, right = node.val, node.left, node.right\n",
    "\n",
    "            if left:\n",
    "                que.append((left, node, 'left'))\n",
    "            if right:\n",
    "                que.append((right, node, 'right'))\n",
    "\n",
    "            if val in to_delete:\n",
    "                if left and left.val not in to_delete:\n",
    "                    res.append(left)\n",
    "                if right and right.val not in to_delete:\n",
    "                    res.append(right)\n",
    "\n",
    "                if child == 'left':\n",
    "                    parent.left = None\n",
    "                if child == 'right':\n",
    "                    parent.right = None\n",
    "\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        res=[]\n",
    "        to_delete = set(to_delete)\n",
    "        def fun(r):\n",
    "            if not r: return None\n",
    "            r.left = fun(r.left)\n",
    "            r.right = fun(r.right)\n",
    "            if r.val in to_delete:\n",
    "                if r.left: res.append(r.left)\n",
    "                if r.right: res.append(r.right)\n",
    "                return None\n",
    "            else:\n",
    "                return r\n",
    "        root = fun(root)\n",
    "        if root: res.append(root)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ret = []\n",
    "        to_delete = set(to_delete)\n",
    "\n",
    "        def dfs(root, is_root, to_delete):\n",
    "            if not root:\n",
    "                return root\n",
    "\n",
    "            delete = root.val in to_delete\n",
    "            root.left = dfs(root.left, delete , to_delete)\n",
    "            root.right = dfs(root.right, delete, to_delete)\n",
    "\n",
    "            if delete:\n",
    "                return None\n",
    "            else:\n",
    "                if is_root:\n",
    "                    ret.append(root)\n",
    "                return root\n",
    "        \n",
    "        dfs(root, True, to_delete)\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans=[]\n",
    "        to_delete=set(to_delete)\n",
    "        def dfs(root,to_delete):\n",
    "                if root.val in to_delete:\n",
    "                    if root.left is root.right:\n",
    "                        return None\n",
    "                    else:\n",
    "                        if root.left: \n",
    "                            if root.left.val not in to_delete:\n",
    "                                 ans.append(root.left)\n",
    "                            dfs(root.left,to_delete)\n",
    "                        if root.right:\n",
    "                            if root.right.val not in to_delete:\n",
    "                                ans.append(root.right)\n",
    "                            dfs(root.right,to_delete)\n",
    "                    root=None\n",
    "                else:\n",
    "                    if root.left is root.right:\n",
    "                        return root\n",
    "                    else:\n",
    "                        if root.left:\n",
    "                            root.left=dfs(root.left,to_delete)\n",
    "                        if root.right:\n",
    "                            root.right=dfs(root.right,to_delete)\n",
    "                        return root\n",
    "\n",
    "\n",
    "        \n",
    "        if dfs(root,to_delete):\n",
    "            ans.append(root)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        to_delete = set(to_delete)\n",
    "\n",
    "        def dfs(node: TreeNode, parent: TreeNode):\n",
    "            if not node:\n",
    "                return\n",
    "            # 递归左右子树\n",
    "            dfs(node.left, node)\n",
    "            dfs(node.right, node)\n",
    "            # 如果当前节点需要被删除\n",
    "            if node.val in to_delete:\n",
    "                # 如果其有父节点，将父节点与其连接断开\n",
    "                if parent:\n",
    "                    if parent.left == node:\n",
    "                        parent.left = None\n",
    "                    else:\n",
    "                        parent.right = None\n",
    "            # 如果当前节点无需删除，同时其父节点为空或者需要被删除\n",
    "            # 则将当前子树分离出来添加到答案中\n",
    "            else:\n",
    "                if (parent and parent.val in to_delete) or not parent:\n",
    "                    ans.append(node)\n",
    "            \n",
    "                    \n",
    "        dfs(root, None)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete)\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node: return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val in s:\n",
    "                if node.left: ans.append(node.left)\n",
    "                if node.right: ans.append(node.right)\n",
    "            else:\n",
    "                return node\n",
    "            return None\n",
    "\n",
    "        if dfs(root): ans.append(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        res = []\n",
    "        s = set(to_delete)\n",
    "        def helper(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "            node.left = helper(node.left)\n",
    "            node.right = helper(node.right)\n",
    "            if node.val in s:\n",
    "                if node.left:\n",
    "                    res.append(node.left)\n",
    "                if node.right:\n",
    "                    res.append(node.right)\n",
    "                return None\n",
    "            else:\n",
    "                return node\n",
    "\n",
    "        if helper(root):res.append(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete)\n",
    "        def dfs(node: Optional[TreeNode]) -> Optional[TreeNode]:\n",
    "            if node is None: return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in s: return node\n",
    "            if node.left: ans.append(node.left)\n",
    "            if node.right: ans.append(node.right)\n",
    "            return None\n",
    "        if dfs(root): ans.append(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        path=[]\n",
    "        table=set()\n",
    "        for to in to_delete:\n",
    "            table.add(to)\n",
    "        def dfs(root: Optional[TreeNode],path: List[int])->TreeNode:\n",
    "            if root is None:\n",
    "                return root\n",
    "            else:\n",
    "                left=dfs(root.left,path)\n",
    "                right=dfs(root.right,path)\n",
    "                root.left=left\n",
    "                root.right=right\n",
    "                if root.val not in table:\n",
    "                    return root\n",
    "                if root.left:\n",
    "                    path.append(root.left)\n",
    "                if root.right:\n",
    "                    path.append(root.right)\n",
    "                return None\n",
    "        Tree=dfs(root,path)\n",
    "        if Tree and Tree.val not in table:\n",
    "            path.append(Tree)\n",
    "        return path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete)\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return None\n",
    "            node.left = dfs(node.left)\n",
    "            node.right = dfs(node.right)\n",
    "            if node.val not in s:\n",
    "                return node\n",
    "            if node.left:\n",
    "                ans.append(node.left)\n",
    "            if node.right:\n",
    "                ans.append(node.right)\n",
    "            return None\n",
    "        if dfs(root):\n",
    "            ans.append(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        \n",
    "        def delNode(prev: Optional[TreeNode], root: Optional[TreeNode]):\n",
    "            if to_delete:\n",
    "                if root.val in to_delete:\n",
    "                    del to_delete[root.val]\n",
    "                    if root in res:\n",
    "                        res.remove(root)\n",
    "                    if prev:\n",
    "                        if prev.left == root:\n",
    "                            prev.left = None\n",
    "                        else:\n",
    "                            prev.right = None\n",
    "                    if root.left:\n",
    "                        res.append(root.left)\n",
    "                        delNode(root,root.left)\n",
    "                    if root.right:\n",
    "                        res.append(root.right)\n",
    "                        delNode(root,root.right)\n",
    "                else:\n",
    "                    if root.left:\n",
    "                        delNode(root,root.left)\n",
    "                    if root.right:\n",
    "                        delNode(root,root.right)\n",
    "\n",
    "\n",
    "        to_delete = {i:1 for i in to_delete}\n",
    "        res = [root]\n",
    "        delNode(None,root)\n",
    "        \n",
    "        return res\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def delNodes(self, root: Optional[TreeNode], to_delete: List[int]) -> List[TreeNode]:\n",
    "        ans = []\n",
    "        s = set(to_delete)  # 哈希表\n",
    "        def dfs(root):  # 返回删除节点后的子树\n",
    "            if root is None:\n",
    "                return None\n",
    "            root.left = dfs(root.left)\n",
    "            root.right = dfs(root.right)\n",
    "            if root.val not in s:  # 不用删除根节点，则直接返回\n",
    "                return root\n",
    "            if root.left: ans.append(root.left)  # 否则将左右子树(如果有的话)加入答案\n",
    "            if root.right: ans.append(root.right)\n",
    "            return None  # 删除根后就不存在了\n",
    "        if dfs(root):  # 如果根没有被删，则加入\n",
    "            ans.append(root)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
